Search results for "Computer and Information Sciences"
showing 10 items of 1328 documents
Variable time amplitude amplification and quantum algorithms for linear algebra problems
2012
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. …
Efficient generation of restricted growth words
2013
A length n restricted growth word is a word w=w"1w"2...w"n over the set of integers where w"1=0 and each w"i, i>1, lies between 0 and the value of a word statistics of the prefix w"1w"2...w"i"-"1 of w, plus one. Restricted growth words simultaneously generalize combinatorial objects as restricted growth functions, staircase words and ascent or binary sequences. Here we give a generic generating algorithm for restricted growth words. It produces a Gray code and runs in constant average time provided that the corresponding statistics has some local properties.
Adjacency matrices of random digraphs: singularity and anti-concentration
2017
Let ${\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$, where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$-regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\approx n/d$. Let $\delta_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $\delta = (\delta_1, …
Restricted compositions and permutations: from old to new Gray codes
2011
Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let @? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of @? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that @? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval si…
Statistics-preserving bijections between classical and cyclic permutations
2012
Recently, Elizalde (2011) [2] has presented a bijection between the set C"n"+"1 of cyclic permutations on {1,2,...,n+1} and the set of permutations on {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. In this paper, we construct a bijection from C"n"+"1 to S"n that preserves the weak excedance set and that transfers quasi-fixed points into fixed points and left-to-right maxima into themselves. This induces a bijection from the set D"n of derangements to the set C"n"+"1^q of cycles without quasi-fixed points that preserves the weak excedance set. Moreover, we exhibit a kind of discrete continuity between C"n"+"1 and S"n that preserves at each s…
Promotion et Développement d'un Master Erasmus Mundus - L'Exemple du VIBOT
2011
Cet article decrit l’offre de formation a l’internationale proposee au Centre Universitaire Condorcet du Creusot (Universite de Bourgogne) dans le domaine de la vision par ordinateur et de la robotique. Il presente l’organisation particuliere de ces formations et les actions de support mises en place pour en assurer la perennite.
Resistive communications based on neuristors
2017
Memristors are passive elements that allow us to store information using a single element per bit. However, this is not the only utility of the memristor. Considering the physical chemical structure of the element used, the memristor can function at the same time as memory and as a communication unit. This paper presents a new approach to the use of the memristor and develops the concept of resistive communication.
Tree Species Classification of Drone Hyperspectral and RGB Imagery with Deep Learning Convolutional Neural Networks
2020
Interest in drone solutions in forestry applications is growing. Using drones, datasets can be captured flexibly and at high spatial and temporal resolutions when needed. In forestry applications, fundamental tasks include the detection of individual trees, tree species classification, biomass estimation, etc. Deep neural networks (DNN) have shown superior results when comparing with conventional machine learning methods such as multi-layer perceptron (MLP) in cases of huge input data. The objective of this research is to investigate 3D convolutional neural networks (3D-CNN) to classify three major tree species in a boreal forest: pine, spruce, and birch. The proposed 3D-CNN models were emp…
Chloroplast genomes of Rubiaceae: Comparative genomics and molecular phylogeny in subfamily Ixoroideae.
2020
In Rubiaceae phylogenetics, the number of markers often proved a limitation with authors failing to provide well-supported trees at tribal and generic levels. A robust phylogeny is a prerequisite to study the evolutionary patterns of traits at different taxonomic levels. Advances in next-generation sequencing technologies have revolutionized biology by providing, at reduced cost, huge amounts of data for an increased number of species. Due to their highly conserved structure, generally recombination-free, and mostly uniparental inheritance, chloroplast DNA sequences have long been used as choice markers for plant phylogeny reconstruction. The main objectives of this study are: 1) to gain in…
Evaluation of chloroplast genome annotation tools and application to analysis of the evolution of coffee species.
2018
International audience; Chloroplast sequences are widely used for phylogenetic analysis due to their high degree of conservation in plants. Whole chloroplast genomes can now be readily obtained for plant species using new sequencing methods, giving invaluable data for plant evolution However new annotation methods are required for the efficient analysis of this data to deliver high quality phylogenetic analyses. In this study, the two main tools for chloroplast genome annotation were compared. More consistent detection and annotation of genes were produced with GeSeq when compared to the currently used Dogma. This suggests that the annotation of most of the previously annotated chloroplast …